{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Perfect Square"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPerfectSquare"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效的完全平方数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数 <code>num</code> 。如果 <code>num</code> 是一个完全平方数，则返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p><strong>完全平方数</strong> 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。</p>\n",
    "\n",
    "<p>不能使用任何内置的库函数，如&nbsp; <code>sqrt</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 16\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>返回 true ，因为 4 * 4 = 16 且 4 是一个整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 14\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-perfect-square](https://leetcode.cn/problems/valid-perfect-square/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-perfect-square](https://leetcode.cn/problems/valid-perfect-square/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['16', '14']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        if num < 2:\n",
    "            return True\n",
    "        left, right = 2, num // 2\n",
    "        if left * left == num or right * right == num:\n",
    "            return True\n",
    "        if left * left > num:\n",
    "            return False\n",
    "        while left <= right:\n",
    "            temp = left + (right - left) // 2\n",
    "            if temp == left:\n",
    "                return False\n",
    "            if temp * temp == num:\n",
    "                return True\n",
    "            elif temp * temp > num:\n",
    "                right = temp\n",
    "            else:\n",
    "                left = temp\n",
    "                \n",
    "        # official implementation of binary search\n",
    "#         if num < 2:\n",
    "#             return True\n",
    "        \n",
    "#         left, right = 2, num // 2\n",
    "        \n",
    "#         while left <= right:\n",
    "#             x = left + (right - left) // 2\n",
    "#             guess_squared = x * x\n",
    "#             if guess_squared == num:\n",
    "#                 return True\n",
    "#             if guess_squared > num:\n",
    "#                 right = x - 1\n",
    "#             else:\n",
    "#                 left = x + 1\n",
    "        \n",
    "#         return False\n",
    "\n",
    "        # Newton's Method ???\n",
    "#         if num < 2:\n",
    "#             return True\n",
    "        \n",
    "#         x = num // 2\n",
    "#         while x * x > num:\n",
    "#             x = (x + num // x) // 2\n",
    "#         return x * x == num\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if num == 1:\n",
    "            return True\n",
    "        low = 0\n",
    "        high = num\n",
    "        medium = (low + high) // 2\n",
    "        while medium * medium != num:\n",
    "            if medium * medium > num:\n",
    "                high = medium\n",
    "                medium = (low + high) // 2\n",
    "\n",
    "            elif medium * medium < num:\n",
    "                low = medium\n",
    "                medium = (low + high) // 2\n",
    "\n",
    "            if low == medium:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: 'int') -> 'bool':\n",
    "        l, r = 1, num\n",
    "        while l <= r:\n",
    "            c = l + (r - l) // 2\n",
    "            if c * c <= num:\n",
    "                l = c + 1\n",
    "            else:\n",
    "                r = c - 1\n",
    "        return (l - 1) * (l - 1) == num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=367 lang=python3\n",
    "#\n",
    "# [367] 有效的完全平方数\n",
    "#\n",
    "# https://leetcode-cn.com/problems/valid-perfect-square/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (39.46%)\n",
    "# Total Accepted:    6K\n",
    "# Total Submissions: 15.3K\n",
    "# Testcase Example:  '16'\n",
    "#\n",
    "# 给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。\n",
    "# \n",
    "# 说明：不要使用任何内置的库函数，如  sqrt。\n",
    "# \n",
    "# 示例 1：\n",
    "# \n",
    "# 输入：16\n",
    "# 输出：True\n",
    "# \n",
    "# 示例 2：\n",
    "# \n",
    "# 输入：14\n",
    "# 输出：False\n",
    "# \n",
    "# \n",
    "#\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: 'int') -> 'bool':\n",
    "        if num == 0 or num == 1 or num == 4: return True\n",
    "        l, r = 1, num\n",
    "        while l <= r:\n",
    "            mid = (l+r)>>1\n",
    "            x = mid*mid\n",
    "            print(mid, x)\n",
    "            if x == num:\n",
    "                return True\n",
    "            elif x < num:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        l = 0\n",
    "        r = num\n",
    "        while l <= r:\n",
    "            m = (l+r) // 2\n",
    "            t = m*m\n",
    "            print(t)\n",
    "            print(l, r)\n",
    "            if t == num:\n",
    "                return True\n",
    "            elif t > num:\n",
    "                r = m-1\n",
    "            else:\n",
    "                l = m+1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        start=0\n",
    "        end=num\n",
    "        while start<end:\n",
    "            mid=(start+end)//2\n",
    "            if mid**2<num:\n",
    "                start=mid+1\n",
    "            elif mid**2>num:\n",
    "                end=mid-1\n",
    "            else:\n",
    "                return True\n",
    "        print(start)\n",
    "        if start**2==num:\n",
    "            \n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        left=0;right=num        \n",
    "        while left<right:            \n",
    "            mid=(left+right)//2            \n",
    "            if num<mid**2:                \n",
    "                right=mid            \n",
    "            else:                \n",
    "                left=mid+1        \n",
    "        if left>1:            \n",
    "            sqrt_num=left-1        \n",
    "        else:            \n",
    "            sqrt_num=left        \n",
    "        return sqrt_num**2==num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "\n",
    "        x1 =(num+1)//2\n",
    "        x2 = x1//2\n",
    "        while True:\n",
    "\n",
    "            if x1**2 == num or x2 **2==num:\n",
    "                return True\n",
    "            if x1**2<num:\n",
    "                x1 =x1*2\n",
    "                x2 =x1\n",
    "            elif x2**2>num:\n",
    "                x1 = x2\n",
    "                x2 = x2//2\n",
    "            elif x1**2>num>x2**2:\n",
    "                for i in range(x2,x1):\n",
    "                    if i**2 == num:\n",
    "\n",
    "                        return True\n",
    "                else:\n",
    "                    return False\n",
    "                    \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        i = 0\n",
    "        while i**2 <= num:\n",
    "            result.append(i**2)\n",
    "            i += 1\n",
    "        if num in result:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        l = 0\n",
    "        r = num\n",
    "        while(l <= r):\n",
    "        \tmid = (l + r) // 2\n",
    "        \tif(mid ** 2 == num):\n",
    "        \t\treturn True\n",
    "        \telif(mid ** 2 > num):\n",
    "        \t\tr = mid - 1\n",
    "        \telse:\n",
    "        \t\tl = mid + 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        if num == 1:\n",
    "            return True\n",
    "        \n",
    "        x = num // 2\n",
    "        while x * x > num:\n",
    "            x = (x + num // x) // 2\n",
    "        return x * x == num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        return int(num**0.5) == num**0.5\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:# 二分查找法\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        start = 1\n",
    "        end = num\n",
    "        if num == 1:\n",
    "            return True\n",
    "        while start < end:\n",
    "            mid = (end + start) // 2\n",
    "            square = mid ** 2\n",
    "            \n",
    "            if square < num:\n",
    "                start = mid + 1\n",
    "            elif square >num:\n",
    "                end = mid \n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        i=1\n",
    "        s=0\n",
    "        while(s<num):\n",
    "            s+=i\n",
    "            i+=2\n",
    "        if(s==num):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        num=pow(num,1/2)\n",
    "        if str(num)[-1] != '0':\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        l, r = 1, num\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if mid * mid < num:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid -1\n",
    "        return l * l == num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        ans=1\n",
    "        pre=0\n",
    "        while abs(ans-pre)>1e-6:\n",
    "            pre=ans\n",
    "            ans=(ans+num/ans)/2\n",
    "        if int(ans)*int(ans)==num:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        p1, p2 = 0, num\n",
    "        while p1 <= p2:\n",
    "            m = (p1 + p2) // 2\n",
    "            print(m)\n",
    "            guess = m * m\n",
    "            if guess > num:\n",
    "                p2 = m - 1\n",
    "            elif guess < num:\n",
    "                p1 = m + 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        n=1\n",
    "        while n*n<num:\n",
    "            n=n+1\n",
    "            print(n)\n",
    "        if n*n==num:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        a = []\n",
    "        for i in range(1,50000):\n",
    "            a.append(i*i)\n",
    "        if num in a:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        if num==1:\n",
    "            return True\n",
    "\n",
    "        if num<2:\n",
    "            return False\n",
    "        s = 2\n",
    "        n = num//2\n",
    "\n",
    "\n",
    "        while s <= n:\n",
    "            mid = (s+n)//2\n",
    "\n",
    "            if mid**2==num:\n",
    "                return True\n",
    "            elif mid**2>num:\n",
    "                n = mid -1 \n",
    "\n",
    "            else:\n",
    "                s = mid +1\n",
    "\n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        left, right = 0, num\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            square = mid * mid\n",
    "            if square < num:\n",
    "                left = mid + 1\n",
    "            elif square > num:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        left=1\n",
    "        right=num//2+1\n",
    "        while left<=right:\n",
    "            mid=(left+right)>>1\n",
    "                           \n",
    "            if mid*mid>num:\n",
    "                right=mid-1\n",
    "            elif mid*mid<num:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "        '''\n",
    "        if left*left==num or (left+1)*(left+1)==num:# or (left-1)*(left-1)==num:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        '''\n",
    "        return False\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        left=1\n",
    "        right=num//2+1\n",
    "        while left<right:\n",
    "            mid=(left+right)>>1\n",
    "                           \n",
    "            if mid*mid>num:\n",
    "                right=mid-1\n",
    "            elif mid*mid<num:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                return True\n",
    "        if left*left==num or (left+1)*(left+1)==num:# or (left-1)*(left-1)==num:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        ans = 0\n",
    "        i = 1\n",
    "        while True:\n",
    "            if i * i > num:\n",
    "                break\n",
    "            ans = i * i\n",
    "            i = i + 1\n",
    "            print(i)\n",
    "            \n",
    "        return ans == num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from xml.dom import minidom\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        l, r = 0, num\n",
    "        while(l <= r):\n",
    "            m = l + (r - l) // 2\n",
    "            if m ** 2 < num:\n",
    "                l = m + 1\n",
    "            elif m ** 2 > num:\n",
    "                r = m - 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        left,right = 1,num\n",
    "\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            mm = mid**2\n",
    "\n",
    "            #print(\"mm=%d\" % (mm))\n",
    "\n",
    "            if mm==num:\n",
    "                return True\n",
    "            elif mm<num:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        if num in (0, 1):\n",
    "            return True\n",
    "        start = 0\n",
    "        end = num//2\n",
    "        middle = start+(end-start)//2\n",
    "        while start <= end:\n",
    "            if middle*middle == num:\n",
    "                return True\n",
    "            elif middle*middle < num:\n",
    "                start = middle+1\n",
    "                middle = start+(end-start)//2\n",
    "            elif middle*middle > num:\n",
    "                end = middle-1\n",
    "                middle = start+(end-start)//2\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPerfectSquare(self, num: int) -> bool:\n",
    "        i = 1\n",
    "        while i * i <= num:\n",
    "            if i * i == num:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        return False "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
